package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.*;

/**
 * 不愧是困难，我上来就被震慑住了，直接抄答案
 */
public class _08_12_8_queen {
    
    /**
     * 挺清晰的这个解法
     */
    static class normal {
        List<List<String>> res = new ArrayList<>();
        int[] rows;
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diags1 = new HashSet<>();
        Set<Integer> diags2 = new HashSet<>();
        char[] t;
        
        public List<List<String>> solveNQueens(int n) {
            rows = new int[n];
            t = new char[n];
            Arrays.fill(t, '.');
            b(0);
            return res;
        }
        
        void b(int row) {
            if (row == rows.length) {
                res.add(dump());
            } else {
                for (int i = 0; i < rows.length; i++) {
                    if (cols.contains(i)) continue;
                    int diag1 = i + row;
                    if (diags1.contains(diag1)) continue;
                    int diag2 = row - i;
                    if (diags2.contains(diag2)) continue;
                    rows[row] = i;
                    cols.add(i);
                    diags1.add(diag1);
                    diags2.add(diag2);
                    b(row + 1);
                    cols.remove(i);
                    diags1.remove(diag1);
                    diags2.remove(diag2);
                }
            }
        }
        
        List<String> dump() {
            List<String> res = new ArrayList<>();
            for (int row : rows) {
                t[row] = 'Q';
                res.add(new String(t));
                t[row] = '.';
            }
            return res;
        }
    }
    
    static class bitwise {
        int[] rows;
        char[] row;
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> solveNQueens(int n) {
            rows = new int[n];
            row = new char[n];
            Arrays.fill(row, '.');
            back(0, 0, 0, 0);
            return res;
        }
        void back(int row, int cols, int diag1, int diag2) {
            if (row == rows.length) {
                res.add(dump());
            } else {
                int bits = ((1 << rows.length) - 1) & ~(cols | diag1 | diag2);
                while (bits != 0) {
                    int lastBit = bits & -bits;
                    bits &= bits - 1;
                    int col = Integer.bitCount( lastBit - 1);
                    rows[row] = col;
                    back(row + 1, cols | lastBit, (diag1 | lastBit) << 1, (diag2 | lastBit) >>> 1);
                }
            }
        }
        List<String> dump() {
            List<String> res = new ArrayList<>();
            for (int rowIndex : rows) {
                row[rowIndex] = 'Q';
                res.add(new String(row));
                row[rowIndex] = '.';
            }
            return res;
        }
    }
}
